package luo.hui.jiang.sort;

import java.util.Arrays;

/**
 * @author 罗惠江
 * @version 1.0
 * @email 1511619294@qq.com
 * @date 2020/7/30 10:10
 */
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = new int[100000];

        for (int i = 0; i < 100000; i++) {
            arr[i] = (int) (Math.random() * 80000000);  //生成随机数组
        }

        long startTime = System.currentTimeMillis();   //获取开始时间
        // System.out.println("排序前~~~");
        // System.out.println(Arrays.toString(arr));
        selectSort(arr);
        // System.out.println("排序后~~~");
        // System.out.println(Arrays.toString(arr));


        long endTime = System.currentTimeMillis(); //获取结束时间
        System.out.println("程序运行时间： " + (endTime - startTime) + "ms");
    }

    /**
     * 选择排序算法的思路：
     * 类似冒泡排序算法，相对于冒泡排序，它需要交换的次数就少很多了。
     * 他是利用了两个中间变量，min 与 minIndex 来实现的。外层遍历来确定我们每个数字都可以排序到。
     * 内层遍历的话，每一次都会选出一个 min 值，minIndex 来存min 对应的数组下标。
     * 然后在循环结束后，我们将 arr[minIndex] = arr[i]; arr[i] = min; 来交换我们数组的位置。
     * 经过一系列的循环操作，最终能确定我们的数组是从大到小，或者从小到大的。
     *
     * @param arr
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = arr[i];
            int min = arr[i];
            for (int j = 0; j < arr.length; j++) {
                if (min > arr[j]) {  // 说明假定的最小值，并不是最小
                    min = arr[j];  // 重置min
                    minIndex = j; // 重置minIndex ，这里死为了后面能进行交换而做的准备
                }
            }
            // 将最小放到a[i] 完成交换
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }
}
